package com.gitee.feizns.explore.data_structure.union_find;

import java.util.HashMap;
import java.util.Map;

/**
 * @author feizns
 * @since 2020/3/13
 */
public class RegionsBySlashes {

    public static void main(String[] args) {
        System.out.println(new RegionsBySlashes().regionsBySlashes(new String[]{"//", "/ "}));
    }

    static char[][] board;
    public static int regionsBySlashes(String[] grid) {
        create(grid);
        Uf uf = new Uf();
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if ( board[i][j] == ' ' ) {
                    int index = index(i, j);
                    int top = top(i, j);
                    int rig = rig(i, j);
                    int bot = bot(i, j);
                    int lef = lef(i, j);
                    if ( top == -1 && rig == -1 && bot == -1 && lef == -1 )
                        uf.add(index);
                    else {
                        if ( top != -1 )
                            uf.union(top, index);
                        if ( rig != -1 )
                            uf.union(rig, index);
                        if ( bot != -1 )
                            uf.union(bot, index);
                        if ( lef != -1 )
                            uf.union(lef, index);
                    }
                }
            }
        }
        return uf.count();
    }

    private static int index(int i, int j) {
        return i * board.length + j;
    }

    private static int top(int i, int j) {
        return i > 0 && board[i - 1][j] == ' ' ? index(i - 1, j) : -1;
    }

    private static int rig(int i, int j) {
        return j < board[0].length - 1 && board[i][j + 1] == ' ' ? index(i, j + 1) : -1;
    }

    private static int bot(int i, int j) {
        return i < board.length -1 && board[i + 1][j] == ' ' ? index(i + 1, j) : -1;
    }

    private static int lef(int i, int j) {
        return j > 0 && board[i][j - 1] == ' ' ? index(i, j - 1) : -1;
    }

    private static void create(String[] grid) {
        int size = 3;
        int N = grid.length;
        board = new char[N * size][N * size];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                char letter = grid[i].charAt(j);
                if ( letter == ' ' ) {
                    board[i * size][j * size] = ' ';
                    board[i * size][j * size + 1] = ' ';
                    board[i * size][j * size + 2] = ' ';
                    board[i * size + 1][j * size] = ' ';
                    board[i * size + 1][j * size + 1] = ' ';
                    board[i * size + 1][j * size + 2] = ' ';
                    board[i * size + 2][j * size] = ' ';
                    board[i * size + 2][j * size + 1] = ' ';
                    board[i * size + 2][j * size + 2] = ' ';
                } else if ( letter == '\\' ) {
                    board[i * size][j * size] = 'X';
                    board[i * size][j * size + 1] = ' ';
                    board[i * size][j * size + 2] = ' ';
                    board[i * size + 1][j * size] = ' ';
                    board[i * size + 1][j * size + 1] = 'X';
                    board[i * size + 1][j * size + 2] = ' ';
                    board[i * size + 2][j * size] = ' ';
                    board[i * size + 2][j * size + 1] = ' ';
                    board[i * size + 2][j * size + 2] = 'X';
                } else if ( letter == '/' ) {
                    board[i * size][j * size] = ' ';
                    board[i * size][j * size + 1] = ' ';
                    board[i * size][j * size + 2] = 'X';
                    board[i * size + 1][j * size] = ' ';
                    board[i * size + 1][j * size + 1] = 'X';
                    board[i * size + 1][j * size + 2] = ' ';
                    board[i * size + 2][j * size] = 'X';
                    board[i * size + 2][j * size + 1] = ' ';
                    board[i * size + 2][j * size + 2] = ' ';
                }
            }
        }
    }

    static class Uf {
        Map<Integer, Integer> parents = new HashMap<>();
        int count;
        void add(int p) {
            if ( !parents.containsKey(p) ) {
                parents.put(p, p);
                count++;
            }
        }
        void union(int p, int q) {
            int pr = find(p);
            int qr = find(q);
            if ( pr != qr ) {
                parents.put(pr, qr);
                count--;
            }
        }
        int find(int p) {
            add(p);
            int val = parents.get(p);
            if ( val != p ) {
                int newP = find(val);
                parents.put(p, newP);
                return newP;
            }
            return val;
        }
        int count() {
            return count;
        }
    }

}
